package datastructure_algorithm.bst;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 二叉树： 
 * 1 二叉树具有唯一根节点 
 * 2 二叉树每个节点最多有两个孩子（左孩子，右孩子） 
 * 3 二叉树每个节点最多有一个父亲 
 * 4 二叉树具有天然递归结构
 * 		1）每个节点的左子树也是二叉树 
 * 		2）每个节点的右子树也是二叉树 
 * 5 二叉树不一定是“满”的 
 * 		1）一个节点也是二叉树 
 * 		2）空也是二叉树
 * 
 * 
 * 二分搜索树（Binary Search Tree）： 
 * 1 二分搜索树是二叉树 
 * 2 二分搜索树的每个节点的值： 
 * 		1）大于其左子树的所有节点的值
 * 		2）小于其右子树的所有节点的值 
 * 3 每一颗子树也是二分搜索树
 * 
 */
public class BST<E extends Comparable<E>> {

	private class Node {
		public E e;
		public Node left, right;

		public Node(E e) {
			this.e = e;
		}
		
		@Override
		public String toString() {
			return "Node(" + e + ")";
		}
		
	}

	private Node root;
	private int size;

	public int size() {
		return size;
	}

	public boolean isEmpty() {
		return size == 0;
	}

	// ************************************* //
	// 比较麻烦的版本
	public void add0(E e) {
		if (root == null) {
			root = new Node(e);
			size++;
		} else 
			add0(root, e);
	}
	private void add0(Node node, E e) {
		// 递归终止条件
		if (e.equals(node.e)) // 当前node等于e，已经存在这个元素，什么都不做
			return;
		else if (e.compareTo(node.e) < 0 && node.left == null) { // 当前node小于e且左边为空，连接上
			node.left = new Node(e);
			size++;
			return;
		} else if (e.compareTo(node.e) > 0 && node.right == null) { // 当前node大于e且右边为空，连接上
			node.right = new Node(e);
			size++;
			return;
		}
		
		// 递归过程
		if (e.compareTo(node.e) < 0)
			add(node.left, e);
		else // e.compareTo(node.e) > 0  等于的情况在终止条件里已经判断过了
			add(node.right, e);
	}
	// ************************************* //
	
	/** 向二分搜索树中添加新的元素e */
	public void add(E e) {
		root = add(root, e);
//		System.out.println(root.e);
	}

	/*
	 * 向以node为根的二分搜索树中插入元素e，递归算法。
	 * 返回插入新节点后二分搜索树的根。
	 * 
	 * 这个版本的二分搜索树不包含重复元素，
	 * 如果想包含重复元素的话，只需要定义： 左子树小于等于节点；或者右子树大于等于节点
	 */
	private Node add(Node node, E e) {
		if (node == null) {
			size++;
			return new Node(e);
		}
		if (e.compareTo(node.e) < 0) {
			node.left = add(node.left, e);
		} else if (e.compareTo(node.e) > 0) {
			node.right = add(node.right, e);
		}
		return node;
	}

	/** 查看二分搜索树中是否包含元素e */
	public boolean contains(E e) {
		return contains(root, e);
	}

	// 查看以root为根的二分搜索树中是否包含元素e，递归算法
	private boolean contains(Node node, E e) {
		if (node == null)
			return false;
		if (e.compareTo(node.e) == 0)
			return true;
		else if (e.compareTo(node.e) < 0)
			return contains(node.left, e);
		else
			return contains(node.right, e);
	}

	/** 二分搜索树的前序遍历 */
	public void preOrder() {
		preOrder(root);
	}

	// 前序遍历以node为根的二分搜索树，递归算法
	private void preOrder(Node node) {
		if (node == null)
			return;
		
		// 访问该节点的代码
		System.out.println(node.e);
		
		preOrder(node.left);
		preOrder(node.right);
	}

	/** 二分搜索树的非递归前序遍历 （深度优先遍历）*/
	public void preOrderNR() {
		// 使用栈结构
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			
			// 访问该节点的代码
			System.out.println(cur.e);
			
			if (cur.right != null)
				stack.push(cur.right);
			if (cur.left != null)
				stack.push(cur.left);
		}
	}
	
	/** 二分搜索树的层序遍历 （广度优先遍历）*/
	public void levelOrder() {
		// 使用队列结构
		Queue<Node> q = new LinkedList<>();
		q.add(root);
		while (!q.isEmpty()) {
			Node cur = q.remove();
			
			// 访问该节点的代码
			System.out.println(cur.e);
			
			if (cur.left != null)
				q.add(cur.left);
			if (cur.right != null)
				q.add(cur.right);
		}
	}

	/** 二分搜索树的中序遍历，会达到排序的效果 */
	public void inOrder() {
		inOrder(root);
	}

	// 中序遍历以root为根的二分搜索树，递归算法
	private void inOrder(Node node) {
		if (node == null)
			return;
		inOrder(node.left);
		
		// 访问该节点的代码
		System.out.println(node.e + " ");
		
		inOrder(node.right);
	}

	/** 二分搜索树的后序遍历 */
	// 后序遍历的一个应用：
	// 为二分搜索树释放内存
	public void postOrder() {
		postOrder(root);
	}

	// 后序遍历以root为根的二分搜索树，递归算法
	private void postOrder(Node node) {
		if (node == null)
			return;
		postOrder(node.left);
		postOrder(node.right);
		
		// 访问该节点的代码
		System.out.println(node.e);
	}

	/** 寻找二分搜索树的最小元素 */
	public E minimum() {
		if (size == 0)
			throw new IllegalArgumentException("BST is empty.");
		return minimum(root).e;
	}

	// 返回以node为根的二分搜索树的最小值所在的节点
	private Node minimum(Node node) {
		return node.left == null ? node : minimum(node.left);
	}

	/** 寻找二分搜索树的最大元素 */
	public E maximum() {
		if (size == 0)
			throw new IllegalArgumentException("BST is empty.");
		return maximum(root).e;
	}

	// 返回以node为根的二分搜索树的最大值所在的节点
	private Node maximum(Node node) {
		return node.right == null ? node : maximum(node.right);
	}

	/** 从二分搜索树中删除最小值所在的节点，并返回最小值 */
	public E removeMin() {
		E ret = minimum();
		root = removeMin(root);
		return ret;
	}

	// 删除以node为根的二分搜索树中的最小节点，并返回删除节点后新的二分搜索树的根
	private Node removeMin(Node node) {
		if (node.left == null) {
			Node rightNode = node.right;
			node.right = null;
			size--;
			return rightNode;
		}
		node.left = removeMin(node.left);
		return node;
	}

	/** 从二分搜索树中删除最大值所在的节点，并返回最大值 */
	public E removeMax() {
		E ret = maximum();
		root = removeMax(root);
		return ret;
	}

	// 删除以node为根的二分搜索树中的最大节点，并返回删除节点后新的二分搜索树的根
	private Node removeMax(Node node) {
		if (node.right == null) {
			Node leftNode = node.left;
			node.left = null;
			size--;
			return leftNode;
		}
		node.right = removeMax(node.right);
		return node;
	}

	/** 从二分搜索树中删除元素为e的节点 */
	public void remove(E e) {
		root = remove(root, e);
	}

	// 删除以node为根的二分搜索树中值为e的节点，并返回删除节点后新的二分搜索树的根
	private Node remove(Node node, E e) {
		if (node == null)
			return null;

		if (e.compareTo(node.e) < 0) {
			node.left = remove(node.left, e);
			return node;
		} else if (e.compareTo(node.e) > 0) {
			node.right = remove(node.right, e);
			return node;
		} else {
			// 待删除节点的左子树为空的情况
			if (node.left == null) {
				Node rightNode = node.right;
				node.right = null;
				size--;
				return rightNode;
			}
			// 待删除节点的右子树为空的情况
			if (node.right == null) {
				Node leftNode = node.left;
				node.left = null;
				size--;
				return leftNode;
			}
			// 待删除节点的左右子树均不为空的情况
			// 找到比删除节点大的最小节点，即待删除节点右子树的最小节点
			// 用这个节点顶替待删除节点的位置
			Node successor = minimum(node.right);
			successor.right = removeMin(node.right);
			successor.left = node.left;

			node.left = node.right = null;
			return successor;
		}
	}

	@Override
	public String toString() {
		StringBuilder sb = new StringBuilder();
		generateBSTString(root, 0, sb);
		return sb.toString();
	}

	// 生成以node为根节点，深度为depth的描述二叉树的字符串
	private void generateBSTString(Node node, int depth, StringBuilder sb) {
		if (node == null) {
			sb.append(generateDepthString(depth) + "null\n");
			return;
		}
		sb.append(generateDepthString(depth) + node.e + "\n");
		generateBSTString(node.left, depth + 1, sb);
		generateBSTString(node.right, depth + 1, sb);
	}

	private String generateDepthString(int depth) {
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < depth; i++) {
			sb.append("--");
		}
		return sb.toString();
	}

}
